package org.example.SolutionNew004;

import java.util.HashSet;
import java.util.Set;

//class Trie {
//    public static void main(String[] args) {
//        Trie trie=new Trie();
//        trie.insert("app");
//        System.out.println(trie.search("app"));
//        System.out.println(trie.startsWith("app"));
//    }
//
//
//    Trie[] trie;
//    Set<String> existElem;  //把set换成boolean，判断是否到结尾
//
//    public Trie() {
//        trie=new Trie[26];
//        existElem=new HashSet<>();
//    }
//
//    public void insert(String word) {
//        existElem.add(word);
//        char[] chars=word.toCharArray();
//        Trie[] temp=trie;
//        for(char c:chars){
//            if(temp[c-'a']==null){
//                Trie tmp=new Trie();
//                temp[c-'a']=tmp;
//            }
//            temp[c-'a']= temp[c-'a']==null?new Trie():temp[c-'a'];
//            temp=temp[c-'a'].trie;
//        }
//    }
//
//    public boolean search(String word) {
//        return existElem.contains(word);
//    }
//
//    public boolean startsWith(String prefix) {
//        char[] chars=prefix.toCharArray();
//        Trie[] temp=trie;
//        for(char c:chars){
//            Trie tmp=temp[c-'a'];
//            if(tmp==null) return false;
//            temp=tmp.trie;
//        }
//        return true;
//    }
//}


class Trie {
    public static void main(String[] args) {
        Trie trie=new Trie();
        trie.insert("app");
        System.out.println(trie.search("app"));
        System.out.println(trie.startsWith("app"));
    }

    Trie[] children;
    boolean valid;

    public Trie() {
        children=new Trie[26];
        valid=false;
    }

    public void insert(String word) {
        if(word.isEmpty()) return;
        Trie node=this;
        for(int i=0;i<word.length();i++){
            if(node.children[word.charAt(i)-'a']==null){
                node.children[word.charAt(i)-'a']=new Trie();
            }
            node=node.children[word.charAt(i)-'a'];
        }
        node.valid=true;
    }

    public boolean search(String word) {
        Trie node=searchPrefix(word);
        return node!=null&&node.valid;
    }

    public boolean startsWith(String prefix) {
        return searchPrefix(prefix)!=null;
    }

    public Trie searchPrefix(String word) {
        if (word.isEmpty()) return null;
        Trie node=this;
        for(int i=0;i<word.length();i++){
            Trie temp=node.children[word.charAt(i)-'a'];
            if(temp==null){
                return null;
            }
            node=temp;
        }
        return node;
    }
}
